package hot100.h0911;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 找到字符串中所有字母异位词
 * @date 2024/9/11 16:46
 */
public class FindAllAnagrams {
    public static void main(String[] args) {

    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        //使用两个数组，记录字母的出现次数
        int[] pCount = new int[26];
        int[] sCount = new int[26]; //记录窗口里面字符的出现次数
        for (int i = 0; i < p.length(); i++) {
            //对应位置字母加一
            pCount[p.charAt(i) - 'a']++;
        }
        int n = p.length();
        for (int i = 0; i < s.length(); i++) {
            sCount[s.charAt(i) - 'a']++;

            if (i >= p.length()) {
                //调整窗口，左移一位，就要使得i-n处的字母--
                sCount[s.charAt(i - n) - 'a']--;
            }

            if (matches(sCount, pCount)) {
                //窗口的第一个索引
                res.add(i - n + 1);
            }
        }
        return res;
    }

    private boolean matches(int[] sCount, int[] pCount) {
        for (int i = 0; i < 26; i++) {
            if (sCount[i]!=pCount[i]){
                return false;
            }
        }
        return true;
    }
}
